package com.example.dynamicprogramming40;

/**
 * 回溯方式，穷举
 * @auther lijiewei
 * @date 2022/3/11 16:43
 */
public class FlashBack {

    //结果放到maxW中
    private int maxW = Integer.MIN_VALUE;
    //物品重量
    private int[] weight = {2, 2, 4, 6, 3};
    //物品个数
    private int n = 5;
    //背包承受的最大重量
    private int w = 9;
    //每次放入背包的物品
    private int[] pack = new int[5];

    /**
     * 穷举所有可能,求最大重量
     * @param i 物品下标序号
     * @param cw 背包中的物品重量
     * @return
     * @author lijiewei
     * @date   2022/3/11 16:51
     */
    public void f(int i, int cw) {
        //重量已经达到承重或者所有物品都考察完了
        if (cw == w || i==n) {
            if(cw > maxW) {
                maxW = cw;
            }
            for (int j = 0; j < pack.length; j++) {
                System.out.print(pack[j]+" ");
            }
            System.out.println();
            return;
        }
        pack[i] = 0;
        //当前物品不装入背包
        f(i+1, cw);
        //判断装入当前物品
        if (cw+weight[i] <= w) {
            pack[i] = 1;
            f(i+1, cw+weight[i]);
        }
    }

    //备忘录，默认值false,记录是否有相应数据
    private boolean[][] mem = new boolean[5][10];

    /**
     * 穷举所有可能,求最大重量,备忘录用于避免重复穷举
     * @param i 物品下标序号
     * @param cw 背包中的物品重量
     * @return
     * @author lijiewei
     * @date   2022/3/19 16:02
     */
    public void f2(int i, int cw) {
        //重量已经达到承重或者所有物品都考察完了
        if (cw == w || i==n) {
            if (cw > maxW) {
                maxW = cw;
            }
            for (int j = 0; j < pack.length; j++) {
                System.out.print(pack[j]+" ");
            }
            System.out.println();
            return;
        }
        pack[i] = 0;
        //重复状态
        if (mem[i][cw]) {
            return;
        }
        //记录(i, cw) 状态
        mem[i][cw] = true;
        //当前物品不装入背包
        f2(i+1, cw);
        //判断装入当前物品
        if (cw + weight[i] <= w) {
            pack[i] = 1;
            f2(i+1, cw+weight[i]);
        }
    }

    //物品价值
    private int[] value = {3, 4, 8, 9, 6};
    //结果放到maxV中
    private int maxV = Integer.MIN_VALUE;

    /**
     * 穷举所有可能,求最大价值,备忘录用于避免重复穷举
     * @param i 物品下标序号
     * @param cw 背包中的物品重量
     * @param cv 背包中的物品价值
     * @return
     * @author lijiewei
     * @date   2022/3/19 16:02
     */
    public void f3(int i, int cw, int cv) {
        //重量已经达到承重或者所有物品都考察完了
        if (cw == w || i == n) {
            if (cv > maxV) {
                maxV = cv;
            }
            for (int j = 0; j < pack.length; j++) {
                System.out.print(pack[j]+" ");
            }
            System.out.println("最大价值："+cv);
            System.out.println();
            return;
        }
        pack[i] = 0;
        //重复状态
        if (mem[i][cw]) {
            return;
        }
        //记录(i, cw) 状态
        mem[i][cw] = true;
        //不装第i个物品
        f3(i+1, cw, cv);
        //判断装入第i个物品
        if (cw + weight[i] <= w) {
            pack[i] = 1;
            f3(i+1, cw+weight[i], cv+value[i]);
        }

    }
}
